package homework.exp03;

import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

/**
 * 计算n条直线（没有三线交于同一点）情况下可能形成的交点个数
 * 解题思想：将问题转化为整数分拆问题
 */
public class H2 {
    static Scanner cin = null;

    // 静态代码块，优先从文件读取输入，失败则从标准输入读取
    static {
        try {
            cin = new Scanner(new FileReader(new File("H.in")));
        } catch (IOException e) {
            cin = new Scanner(System.in);
        }
    }

    /**
     * 主函数
     * 读取输入n，调用dfs进行整数分拆，然后输出所有可能的交点数
     */
    public static void main(String[] args) {
        // 处理每个输入的n
        while (cin.hasNext()) {
            int n = cin.nextInt();
            // 使用DFS进行整数分拆，计算所有可能的交点数
            dfs(n, 0);
            // 输出结果：遍历所有可能的交点数，输出被标记为可能的交点数
            // 最大可能交点数是n*(n-1)/2（所有直线两两相交）
            for (int i = 0; i <= n * (n - 1) / 2; i++) {
                if (dp[n][i] == 1) {
                    System.out.print(i + " ");
                }
            }
            System.out.println();
        }
    }

    /**
     * dp[n][i] = 1 表示n条直线可以形成i个交点
     * 数组大小设为22x200，因为题目中n最大不会太大（根据问题规模估算）
     */
    static int[][] dp = new int[22][200];
    
    /**
     * 用于存储当前整数分拆方案的临时数组
     * a[k]表示第k组直线的数量（具有相同斜率的直线数量）
     */
    static int[] a = new int[22];

    /**
     * 深度优先搜索函数，用于整数分拆
     * @param n 总直线数
     * @param k 当前分拆的组索引
     */
    private static void dfs(int n, int k) {
        // 计算当前已分拆各组直线的总数
        int s = 0;
        for (int i = 0; i < k; i++) {
            s += a[i];
        }
        
        // 递归终止条件：已分拆的直线数大于等于n
        if (s >= n) {
            // 如果刚好等于n，则计算对应的交点数
            if (s == n) {
                // n = a[0] + a[1] + ... + a[k-1]，表示n条直线分成k组，每组a[i]条平行直线
                
                // 计算交点数：每组直线与其他组直线相交产生的交点数之和
                int tot = 0; // 总交点数
                int b = a[0]; // 已计算的直线总数
                
                // 遍历每个后续组，计算该组与前面所有组的交点数
                for (int i = 1; i <= k - 1; i++) {
                    // 交点数 = 前面所有直线数 * 当前组的直线数
                    tot += b * a[i];
                    // 更新已计算的直线总数
                    b += a[i];
                }
                
                // 标记这种交点数是可能的
                dp[n][tot] = 1;
            }
            return;
        }

        // 尝试将n-s分成若干部分，作为新的一组
        // 为了避免重复计算相同的分拆（只是顺序不同），限制新添加的数不大于上一个数
        for (int i = n; i >= 1; i--) {
            // 避免重复：如果不是第一组，则新组的大小不能超过前一组
            if (k >= 1 && i > a[k - 1]) continue;
            
            // 设置当前组的大小
            a[k] = i;
            // 递归处理下一组
            dfs(n, k + 1);
        }
    }
}